#pragma once

#include <vector>

using namespace std;

class MatrixGraph {

    int numIslands(vector<vector<char>>& grid) {
        size_t m = grid.size(), n = grid[0].size();
        int directions[][2] = { {-1, 0}, {0, -1}, {0, 1}, {1, 0} };

        function<void(int, int)> dfs = [&](int i, int j) {
            grid[i][j] = '0';
            for (size_t k = 0; k < 4; k++)
            {
                int ni = i + directions[k][0], nj = j + directions[k][1];
                if (ni >= 0 && ni < m && nj >= 0 && nj < n && grid[ni][nj] == '1')
                {
                    dfs(ni, nj);
                }
            }
            };

        int islandCount = 0;
        for (size_t i = 0; i < m; i++)
        {
            for (size_t j = 0; j < n; ++j) {
                if (grid[i][j] == '1') {
                    ++islandCount;
                    dfs(i, j);
                }
            }
        }
        return islandCount;
    }

    int numEnclaves(vector<vector<int>>& grid) {
        class UnionFind {
        private:
            vector<int> parent;
            vector<int> rank;
            vector<bool> onEdge;

        public:
            UnionFind(const vector < vector<int>>& grid) {
                size_t m = grid.size(), n = grid[0].size();
                int count = m * n;
                this->parent = vector<int>(count);
                this->rank = vector<int>(count);
                this->onEdge = vector<bool>(count, false);

                for (size_t i = 0; i < m; i++)
                {
                    for (size_t j = 0; j < n; j++)
                    {
                        int index = i * n + j;
                        if (grid[i][j] == 1) {
                            this->parent[index] = index;
                            if (i == 0 || i == m - 1 || j == 0 || j == n - 1)
                            {
                                this->onEdge[index] = true;
                            }
                        }
                        this->rank[index] = 0;
                    }
                }
            }

            int find(int index) {
                if (index != parent[index])
                {
                    parent[index] = find(parent[index]);
                }
                return parent[index];
            }

            void uni_on(int x, int y) {
                int rootX = this->find(x), rootY = find(y);
                if (rootX != rootY)
                {
                    if (rank[rootX] > rank[rootY])
                    {
                        this->parent[rootY] = rootX;
                        this->onEdge[rootX] = this->onEdge[rootX] || this->onEdge[rootY];
                    }
                    else if (rank[rootX] < rank[rootY])
                    {
                        parent[rootX] = rootY;
                        onEdge[rootY] = onEdge[rootX] || onEdge[rootY];
                    }
                    else {
                        parent[rootX] = rootY;
                        onEdge[rootY] = onEdge[rootX] || onEdge[rootY];
                        rank[rootY] += 1;
                    }
                }
            }

            bool isOnEdge(int index) {
                return onEdge[find(index)];
            }
        };
        size_t m = grid.size(), n = grid[0].size();
        UnionFind unionFind(grid);
        for (size_t i = 0; i < m - 1; i++)
        {
            for (size_t j = 0; j < n - 1; ++j) {
                if (grid[i][j] == 1)
                {
                    int index = i * n + j;
                    if (grid[i + 1][j] == 1)
                        unionFind.uni_on(index, index + n);
                    if (grid[i][j + 1] == 1)
                        unionFind.uni_on(index, index + 1);
                }
            }
        }

        int enclavesCount = 0;
        for (size_t i = 1; i < m - 1; i++)
        {
            for (size_t j = 1; j < n - 1; j++)
            {
                if (grid[i][j] == 1 && !unionFind.isOnEdge(i * n + j))
                    ++enclavesCount;
            }
        }
        return enclavesCount;
    }


};